package com.lw.leetcode.arr.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * c
 * arr
 * 面试题 17.26. 稀疏相似度
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/2 11:34
 */
public class ComputeSimilarities {

    public List<String> computeSimilarities(int[][] docs) {
        List<String> list = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = docs.length;
        for (int i = 0; i < length; i++) {
            for (int t : docs[i]) {
                map.computeIfAbsent(t, v -> new ArrayList<>()).add(i);
            }
        }
        int[] counts = new int[length * length];
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> value = entry.getValue();
            int size = value.size();
            for (int i = 1; i < size; i++) {
                for (int j = 0; j < i; j++) {
                    counts[value.get(i) * length + value.get(j)]++;
                }
            }
        }
        for (int i = length * length - 1; i >= 0; i--) {
            if (counts[i] == 0) {
                continue;
            }
            int t1 = i / length;
            int t2 = i % length;
            double c = (double) counts[i] / (docs[t1].length + docs[t2].length - counts[i]);
            list.add(String.format("%s,%s: %.4f", Math.min(t1, t2), Math.max(t1, t2), c));
        }
        return list;
    }

}
